package solution;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by wangxingsheng on 2022/6/20.
 * 素数组合
 *
 * 22
 20923 22855 2817 1447 29277 19736 20227 22422 24712 27054 27050 18272 5477 27174 13880 15730 7982 11464 27483 19563 5998 16163
 */
public class SuCompCount {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        ArrayList<Integer> l1 = new ArrayList<>();
        ArrayList<Integer> l2 = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            int input = in.nextInt();
            if (input % 2 == 0) {
                l2.add(input);
            } else {
                l1.add(input);
            }
        }
        //System.out.println("----------------------way1:");
        //way1(l1,l2);
        //System.out.println();
        //System.out.println("----------------------way2:");
        way2(l1,l2);
    }
    private static void way1(ArrayList<Integer> l1, ArrayList<Integer> l2){
        int[] r1 = new int[l1.size() + 1];
        int[] r2 = new int[l2.size() + 1];
        int compCount = 0;
        for (int i = 1; i < l1.size() + 1; i++) {
            if (findComp(i, l1, l2, r1, r2)) {
                compCount++;
            }
        }
        System.out.println(compCount);
    }

    private static boolean findComp(int i, ArrayList<Integer> l1, ArrayList<Integer> l2, int[] r1, int[] r2) {
        for (int j = 1; j < l2.size() + 1; j++) {
            int v1 = l1.get(i - 1);
            int v2 = l2.get(j - 1);
            if (isPrime(v1 + v2) && r2[j] == 0) {
                r2[j] = i;
                if (r1[i] == 0 || findComp(i, l1, l2, r1, r2)) {
                    r1[i] = j;
                    //System.out.println("c:( [" + i + "]" + v1 + ", [" + j + "]" + v2 + " )");
                    return true;
                }
            }
        }
        return false;
    }

    private static void way2(ArrayList<Integer> l1, ArrayList<Integer> l2){
        int[] record = new int[l2.size()];
        int compCount = 0;
        for (int i : l1) {
            boolean[] flag = new boolean[l2.size()];
            if (findComp2(i, l2, record, flag)) {
                compCount++;
            }
        }
        System.out.println(compCount);
    }

    private static boolean findComp2(int v1, ArrayList<Integer> l2, int[] record, boolean[] flag) {
        for (int j = 0; j < l2.size(); j++) {
            int v2 = l2.get(j);
            if (isPrime(v1 + v2) && !flag[j]) {
                flag[j] = true;
                if (record[j] == 0) {
                    record[j] = v1;
                    //System.out.println("c:( [-]" + v1 + ", [" + (j+1) + "]" + v2 + " )");
                    return true;
                }else if(findComp2(record[j], l2, record, flag)){
                    record[j] = v1;
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isPrime(int n) {
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}
